package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
硬币问题
有1元,5元,10元,50元,100元,500元的硬币各c1,c5,c10,c50,c100,c500枚.
现在要用这些硬币来支付A元,最少需要多少枚硬币?

假定本题至少存在一种支付方案.
0 ≤ ci ≤ 10^9
0 ≤ A ≤ 10^9

输入:
第一行有六个数字,分别代表从小到大6种面值的硬币的个数
第二行为A,代表需支付的A元

样例:
输入
3 2 1 3 0 2
620
输出
6
 */
public class a硬币支付by贪心 {
	public static void main(String[] args) {
		a硬币支付by贪心 test = new a硬币支付by贪心();
		test.useGreedyAlgorithmCion();
	}
	
	
	/**
	 * 前置方法
	 */
	public void useGreedyAlgorithmCion() {
		int[] coins = new int[] {1, 5, 10, 50, 100, 500};
		int[] typeNumber = new int[6];
		Scanner scanner = new Scanner(System.in);
		for (int i = 0; i < typeNumber.length; i++) {
			typeNumber[i] = scanner.nextInt();
		}
		int remainder = scanner.nextInt();
		int res = GreedyAlgorithmCion(coins, typeNumber, remainder, 5);
		System.out.println(res);
	}
	
	/**
	 * 递归形式
	 * 可以让对方找我钱
	 * 因为本题题目中明确，题目是有解的，所以当递归到需要使用1元的时候，直接返回remainder
	 * @param coins
	 * @param typeNumber
	 * @param remainder
	 * @param current
	 * @return
	 */
	public int GreedyAlgorithmCion(int[] coins, int[] typeNumber, int remainder, int current) {
		if (remainder <= 0) {
			return 0;
		}
		if (current == 0) {
			return remainder;//因为本题题目中明确，题目是有解的，所以当递归到需要使用1元的时候，直接返回remainder
		}
		int coinValue = coins[current];
		int coinNumber = typeNumber[current];
		int actualUse = Math.min(remainder / coinValue, coinNumber);
		return actualUse + GreedyAlgorithmCion(coins, typeNumber, remainder - actualUse * coinValue, current - 1);
	}
}
